package org.atovio.structure.adt;

/**
 * 图接口
 * @author AtoVio, Winter Yuan
 * @version 1.0
 */
public interface Graph<T> {
    // 返回顶点数
    int vertexCount();
    // 返回顶点i
    T get(int i);
    // 设置顶点i元素为value
    void set(int i, T value);
    // 插入值为value的顶点，返回顶点序号
    int insert(T value);
    // 插入边，权值为w
    void insert(int i, int j, int w);
    // 删除顶点i及与其相关的边
    T remove(int i);
    // 删除边
    void remove(int i, int j);
    // 查找并返回首个与key相等的元素的序号
    int search(T key);
    // 查找并删除与key相等的顶点及其相关联的边
    T remove(T key);
    // 返回权值
    int weight(int i, int j);

    /*
    从顶点i出发的深度优先遍历
     */
    void DFSTraverse(int i);
    /*
    从顶点i出发的广度优先遍历
     */
    void BFSTraverse(int i);
    /*
    构造带权无向图的最小生成树，Prim算法
     */
    void minSpanTree();
    /*
    求带权图顶点i的单源最短路径，Dijkstra算法
     */
    void shortestPath(int i);
    /*
    求带权图每对顶点间的最短路径及长度,Floyd算法
     */
    void shortestPath();
}
